package a_doubleWrite;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 139,140
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-07-27 19:04
 */
public class L139 {
    List<String> list = new ArrayList<>();

    public List<String> wordBreak(String s, List<String> wordDict) {
        if (s.length() == 0) return list;
        //使用set快速判断
        Set<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = i - 1; j >= 0; j--) {
                dp[i] = dp[j] && set.contains(s.substring(j, i));
                if (dp[i]) break;//找到一个立马退出，防止覆盖
            }
        }
        //不能构成，直接返回
        if (!dp[s.length()]) return list;
        //递归
        dfs(s, set, 0, new ArrayList<>());
        return list;
    }

    /**
     * 递归回溯
     *
     * @param s     字符串
     * @param set   字符set
     * @param index 字符索引
     * @param clist 字符集合
     * @return void
     */
    private void dfs(String s, Set<String> set, int index, List<String> clist) {
        if (index == s.length()) {
            list.add(String.join(" ", new ArrayList<>(clist)));
            return;
        }
        for (int i = index; i < s.length(); i++) {
            String substring = s.substring(index, i + 1);
            if (!set.contains(substring)) continue;
            clist.add(substring);
            dfs(s, set, i + 1, clist);
            clist.remove(clist.size() - 1);
        }
    }

    public static void main(String[] args) {
        L139 l139 = new L139();
        ArrayList<String> objects = new ArrayList<>();
        objects.add("aa");
        objects.add("aas");
        String join = String.join(" ", objects);
        System.out.println(join);
    }
}
